講義名 計算基礎論 　(Foundations of Computing)
開講学期 3 学期 単位数 2--1--0
担当教官 （Eクラス）：佐伯　元司 教授　　西8E棟 9階 902号室　　内線：2192
（Oクラス）：尾形わかは 助教授　　南3棟 5階 511号室　　内線：3500
講義の目的 計算の原理，計算モデルを様々な角度から述べ，“計算”の本質を講義していく． さらに計算効率の測り方など計算の複雑さの解析の導入も行なう．
知識
ユニット
  • 計算モデル（帰納的関数，ラムダ-計算，チューリング機械）
  • 計算の原理（計算可能性，Kleene の定理，while と for-times の違い）
関連科目・
履修条件等		 <--- 　 情報基礎学
---> 　 数理論理学， オートマトンと言語， プログラミング第一
<--> 　 情報工学実験第一
教科書
  • 計算論入門，渡辺 治，米崎 直樹 著，日本評論社，1996
参考書
  • 計算論 --- 計算可能性とラムダ計算 ---，高橋 正子 著，近代科学社，1991
  • 計算可能性入門，小林 孝次郎 著，近代科学社, 1980
講義計画
  1. チューリング機械への導入（計算モデルとして）
  2. チューリング機械によるプログラミング
  3. 多テープ・チューリング機械
  4. チューリング機械による計算可能性，計算不可能性
  5. 帰納的関数への導入（計算モデルとして）
  6. 帰納的関数によるプログラミング
  7. 中間試験
  8. ゲーデル数によるコード化
  9. 帰納的関数による計算可能性，計算不可能性
  10. ラムダ-計算への導入
  11. ラムダ-式によるプログラミング
成績評価 演習，中間試験，期末試験により評価する．
試験問題・
略解の公開 		（Oクラス）：試験終了後に直接配布
担当教官
からの一言 		特になし
関連サイト 特になし


インデックスへ戻る